#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2025/3/17
# @USER    : Shengji He
# @File    : PalindromeSubsets.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
"""
- Dynamic Programming
- Recursive
"""
from typing import List


class Solution:
    """
    Given a string s, return all the palindromic subsets (the order of the subsets does not matter) of s.
    A string is a subset of another string if it can be obtained after deleting some (or zero) characters from the other string.

    A palindrome is a word that reads the same backward as forward.

    Example 1:
        Input: s = "aab"
        Output: [["a","a","b"],["aa","b"]]

    Example 2:
        Input: s = "a"
        Output: [["a"]]
    """

    @staticmethod
    def is_palindrome(s: str) -> bool:
        return s == s[::-1]

    @staticmethod
    def find_sub_str(s: str):
        num = len(s)
        if num < 2:
            return [s]
        output = []
        for i in range(1, num + 1):
            prefix_str = s[:i]
            remainder_str = s[i:]
            if Solution.is_palindrome(prefix_str):
                remainder_out = Solution.find_sub_str(remainder_str)

                for v in remainder_out:
                    if isinstance(v, str):
                        if len(v) > 0:
                            output.append([prefix_str, v])
                        else:
                            output.append([prefix_str])
                    else:
                        output.append([prefix_str] + v)
        return output

    def palindromeSubsets(self, s: str) -> List[List[str]]:
        """recursive"""
        if len(s) < 2:
            return [[s]]
        out = Solution.find_sub_str(s)
        return out

    def palindromeSubsets_v2(self, s: str) -> List[List[str]]:
        """dynamic programming"""
        num = len(s)
        if num < 2:
            return [[s]]
        dp_list = [[-1] * num for i in range(num)]

        def search_sub_str(left_idx: int, right_idx: int):
            if left_idx > right_idx:
                return ['']
            cur_out = []
            for i in range(left_idx, right_idx + 1):
                prefix_str = s[left_idx: i + 1]
                if dp_list[left_idx][i] == -1:
                    if Solution.is_palindrome(prefix_str):
                        dp_list[left_idx][i] = 1
                    else:
                        dp_list[left_idx][i] = 0
                if dp_list[left_idx][i] == 1:
                    remainder_out = search_sub_str(i + 1, right_idx)
                    for v in remainder_out:
                        if isinstance(v, str):
                            if len(v) > 0:
                                cur_out.append([prefix_str, v])
                            else:
                                cur_out.append([prefix_str])
                        else:
                            cur_out.append([prefix_str] + v)
            return cur_out

        output = search_sub_str(0, num - 1)
        return output

    def palindromeSubsets_v3(self, s: str) -> List[List[str]]:
        """KMP"""
        n = len(s)
        dp = [[False] * n for _ in range(n)]

        # preprocessing dp,s[i..j] is palindrome?
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j]:
                    if j - i <= 1:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]

        result = []

        def backtrack(start, path):
            if start == n:
                result.append(path.copy())
                return
            for end in range(start, n):
                if dp[start][end]:
                    path.append(s[start:end + 1])
                    backtrack(end + 1, path)
                    path.pop()

        backtrack(0, [])
        return result


if __name__ == '__main__':
    s = "aabaa"
    S = Solution()
    print(S.palindromeSubsets(s))
    # print(S.palindromeSubsets_v2(s))
    print(S.palindromeSubsets_v3(s))
    print('done')
